【图论笔记】拓扑图论（1）：曲面与拓扑图

曲面拓扑是拓扑图论的基础。当然即使我们不熟悉曲面拓扑的理论，也仍然不妨碍我们研究拓扑图论，毕竟拓扑图论上所用的拓扑学只是一点点。

---

目录

• 1. 曲面与平面
• 2. 画在曲面上的图
• 3. 图的嵌入和拓扑图
• 4. 平面图与可平面性
• 返回【图论笔记】

---

1. 曲面与曲线

设$\Gamma$是一个豪斯多夫空间．如果$\Gamma$上的每一个点都有一个开邻域同胚于欧氏平面$\mathbb{E}^2$中的开圆盘，那么我们就说$\Gamma$是一个二维流形．

设$\Gamma$是一个二维流形，而$f$是一个从闭区间$[0,1]$到$\Gamma$的连续映射．我们令$A=f([0,1])$．那么我们就说$A$是$\Gamma$上的一条曲线，其中$f(0)$和$f(1)$就是曲线$A$的端点；如果$f$是单射，那么$A$就是一条简单曲线；如果$A$的两个端点是重合的，那么$A$就是一条闭曲线；如果$f$在开区间$(0,1)$上是单射并且$A$的两个端点重合，那么$A$就是一条简单闭曲线．设$0\le a<b\le1$．如果$A$不是闭曲线，那么，$f([a,b])$就是曲线$A$上从$f(a)$到$f(b)$的一个曲线段；如果$A$是闭曲线，那么，$f([a,b])$或$f([0,a]\cup[b,1])$就是曲线$A$上从$f(a)$到$f(b)$的一个曲线段．

如果二维流形$\Gamma$上任意两点间总有一条简单曲线连接，那么我们就说$\Gamma$是弧连通的．但是，二维流形未必都是弧连通的．在包含意义下极大的弧连通子集被称为区域．如果$\Gamma$中任意开覆盖都有有限子覆盖，则称$\Gamma$是紧致的．紧致的、弧连通的二维流形就是曲面．没有边界的曲面称为闭曲面．欧氏平面是二维流形但不是曲面，因为它无界因而不紧致；莫比乌斯带是曲面但不是闭曲面，因为它有边界；球面、环面、射影平面、克莱因瓶都是常见的闭曲面．

根据著名的闭曲面的分类定理，我们知道：任何闭曲面总是可以通过给球面添加环柄和交叉帽来得到．设闭曲面$\Gamma$是从球面添加$h$个环柄和$c$个交叉帽得到的．当且仅当$c=0$时，$\Gamma$才是可定向的曲面．令${\rm eg}(\Gamma)=2h+c$，我们称之为闭曲面$\Gamma$的欧拉亏格．一般所说的欧拉示性数是$\chi(\Gamma)=2-{\rm eg}(\Gamma)$，在拓扑图论中通常回避这个参数．众所周知，借助球极射影，可以将删除一点（北极）后的球面与欧氏平面建立同胚关系，所以，我们规定欧氏平面的欧拉亏格与球面相同，即${\rm eg}(\mathbb{E}^2)=0$．在以后的讨论中，我们简称欧氏平面为平面．

---

2. 画在曲面上的图

设$\Gamma$是一个闭曲面或平面，$G$是一个图．$G$的$\Gamma$-画法是由两个单射$\varphi$和$\psi$构成的有序对，记作$D(\varphi,\psi)$，简记作$D$．其中，$\varphi$将$G$的顶点映射为$\Gamma$的点，我们仍然称$\varphi$的像是$D$的顶点；而$\psi$将$G$的边映射为连接相应顶点的简单曲线（环被映射为简单闭曲线），我们仍然称$\psi$的像是$D$的边．$D$的顶点的全体记作$V(D)$，$D$的边的全体记作$E(D)$．设$p\in \Gamma$，$e\in E(G)$．如果$p\in \psi(e)$且不是$\psi(e)$的端点，那么我们说$\psi(e)$穿过点$p$．如果$G$的$\Gamma$-画法$D$还满足：

• 任意边不穿过顶点，
• 任意两边不相切，
• 任意两边公共点有限，
• 任意三边不穿过同一点，

那么我们就说$D$是$G$的正规$\Gamma$-画法．

设$D$是图$G$的正规$\Gamma$-画法，$e_1,e_2\in E(G)$，$p\in \Gamma$．如果$\psi(e_1),\psi(e_2)$都穿过$p$，就说$e_1$和$e_2$在$D$上交叉于$p$，也说$p$是$D$的一个交叉．$D$上交叉的全体叫做$D$的交叉集，记作${\rm CR}_{\Gamma}(D)$．$D$上交叉的总数叫做$D$的交叉数，记作${\rm cr}_{\Gamma}(D)$．设$\mathcal{D}$是$G$的所有正规$\Gamma$-画法的全体．定义$G$在$\Gamma$上的交叉数为
${\rm cr}_\Gamma(G)=\min_{D\in \mathcal{D}}{\rm cr}_\Gamma(D).$ 如果$D$是使得${\rm cr}_\Gamma(D)={\rm cr}_\Gamma(G)$的正规$\Gamma$-画法，那么我们就称$D$是$G$在$\Gamma$上的cr-最小画法．求图$G$在$\Gamma$上的交叉数和cr-最小画法的问题，就是图交叉数问题．

设$S\subseteq \Gamma$，令${\rm CR}_{\Gamma,D}(S)={\rm CR}_\Gamma(D)\cap S$，令${\rm CR}_{\Gamma,D}(S)=|{\rm CR}_{\Gamma,D}(S)|$．例如，在正规$\Gamma$-画法$D$上，边$e\in E(D)$上所包含的交叉的集合和个数，就可以分别记作：${\rm CR}_{\Gamma,D}(e)$和${\rm cr}_{\Gamma,D}(e)$．

特别地，如果$\Gamma$是平面$\mathbb{E}^2$，那么，上述符号中的$\Gamma$通常省略；上述术语中的$\Gamma$通常换成“平面”．所以${\rm CR}_{\mathbb{E}^2}(\cdot)$和${\rm cr}_{\mathbb{E}^2}(\cdot)$一般也写成${\rm CR}(\cdot)$和${\rm cr}(\cdot)$．

在图$G$的$\Gamma$-画法$D$中，由于图$G$的边被映射成了简单曲线或简单闭曲线，所以$D$的任何边不会和自己交叉．

---

3. 图的嵌入和拓扑图

设$\Gamma$是一个闭曲面或平面，$G$是一个图，$D$是$G$的一个正规$\Gamma$-画法．如果$D$没有交叉，我们就说$D$是$G$的一个==$\Gamma$-嵌入==，也说$G$通过$D$嵌入到$\Gamma$上．当$\Gamma$是平面时，我们称$\Gamma$-嵌入为平面嵌入．称能嵌入平面的图为可平面图．如果固定图$G$的$\Gamma$-嵌入$D$，并将$G$与$D$等同看待，那么$G$的顶点和边分别可以看成$\Gamma$上的相应点和相应简单（闭）曲线，此时我们称$G$为$\Gamma$上的拓扑图；特别地，如果$\Gamma$是平面，那么就称拓扑图$G$为平面图．

可平面图和平面图是不同的．一个可平面图可能有多种平面嵌入，而平面图则固定了一种平面嵌入；一个可平面图本质上仍然是由顶点集和边集构成的有序二元组，而平面图实际上是一种拓扑图，它是由顶点集、边集和面集构成的有序三元组$G(V,E,F)$．

设$G$是$\Gamma$上的一个拓扑图．我们称
$\Gamma\setminus\bigcup_{e\in E(G)}e$
的区域（即极大弧连通子集）为$G$的面．$G$的面集用$F(G)$或$F$表示，面数用$f(G)$表示．设$f\in F(G)$．$f$的边界记作$\partial(f)$．$\partial(f)$可以看作$G$的一个拓扑子图，但未必是连通图．实际上，当且仅当$G$连通时，$G$的每个面的边界才都是连通图．如果$\partial(f)$只有一个连通分支，那么$\partial(f)$显然是一条闭游走(closed walk)，我们称之为$f$的边界闭游走；$f$的边界闭游走的长度称为$f$的度，记作$d(f)$．$d(f)$不一定等于$f$所关联的边数．这是因为：如果$f$关联了割边$e$，那么$e$两侧都是$f$，这导致$e$在$\partial(f)$中会出现两次．但这并不影响握手定理的成立．

（面边）握手定理 如果$G$是平面图，那么$\sum_{f\in F(G)}\deg(f)=2e(G).$

如果$\partial(f)$是一个圈，那么我们称这个圈是一个面圈．同样因为$f$可能关联割边，所以边界闭游走不一定是圈，除非$G$是2-连通的．

Whitney定理 除$K_1$和$K_2$外，$2$-连通的平面图的每个面的边界都是圈．

Whitney定理的推论 无环$3$-连通的平面图的任何顶点的邻域都会构成一个圈．

一般来讲，如果$G$有一个$\Gamma$-嵌入，使得每个面都同胚于圆盘，则称这个嵌入是一个2-腔胞嵌入．什么图在什么闭曲面上会有2-腔胞嵌入，这是拓扑图论的一个重要研究课题，此处不便展开．

关于顶点、边、面三者之间的数量关系有著名的Eular-Poinare公式．

Eular-Poinare公式 如果$\Gamma$上拓扑图$G$是连通的，那么$v(G)-e(G)+f(G)=2-{\rm eg}(\Gamma)$．

将Eular-Poinare公式限制在平面图上使用（此时一般称为Eular公式）可以得到如下两个常用推论．

推论1. 如果$G$是至少$3$个顶点的简单可平面图，那么$e(G)\le 3v(G)-6$，其中等号成立当且仅当$G$的每个平面嵌入都是三角剖分（即每个面的边界都是$3$-圈的平面嵌入）．

推论2. 每个简单可平面图最小度都不超过$5$．

---

4. 平面图与可平面性

设$A$是平面$\mathbb{E}^2$上的曲线．如果$A$是平面上有限个直线段的并，那么我们称$A$是平面上的一条折线．类似地，我们可以定义闭折线．如果$A$既是简单曲线又是折线，那么我们就称$A$是简单折线；同样地，如果$A$既是简单闭曲线又是折线，那么我们就称$A$是简单闭折线．

引理1. 设$\Omega$是平面上的一个弧连通的开集．那么$\Omega$内任意两点都可以被$\Omega$内的一条简单折线连接．

证明. 任取$x,y\in \Omega$．因为$\Omega$是弧连通的，所以$\Omega$中存在连接$x,y$的简单曲线$A$．对每个$z\in A$，存在以$z$为心的开的圆盘$B(z)\subseteq \Omega$，所以$\{B(z):z\in A\}$是$A$的一个开覆盖．因为连续映射保持紧致性，所以$A$在$\Omega$上是紧致的．所以$\{B(z):z\in A\}$有一个有限子覆盖，记作$\{B(z_i):i=1,2,\dots,k\}$．这样就很容易构造包含于$\cup_{i=1}^kB(z_i)$的、连接$x,y$的折线了．$\Box$

使用引理1，很容易证明如下引理．

引理2. 任何可平面图都有一个平面嵌入，使得每条边都是简单折线．

事实上还可以进一步证明，任何可平面图都有一个直线平面嵌入，也就是每个边都是直线段的嵌入．这个定理证明很复杂，这里不予给出．

直线嵌入定理 任何可平面图都有一个平面嵌入，使得每条边都是直线段．

使用引理1，还能证明著名的Jordan曲线定理．它的证明极其繁琐复杂，我们在这里不予给出．

Jordan曲线定理 平面$\mathbb{E}^2$上任何简单闭曲线$C$的补是两个区域，一个有界，一个无界．

Jordan曲线定理事实上表明，$\mathbb{E}^2$上任何两个只有有限个公共点的简单曲线必然相交偶数次．

需要注意的是：Jordan曲线定理在闭曲面上并不成立．比如球面上的简单闭曲线分出两个有界的区域．环面的经线和纬线都只能分出一个区域．

设$C$是平面$\mathbb{E}^2$上的一条简单闭曲线，由Jordan曲线定理可知，$\mathbb{E}^2\setminus C$是两个区域，其中有界的区域称为$C$的内域，记作${\rm Int}(C)$，无界的区域称为$C$的外域，记作${\rm Ext}(C)$．
特别地，如果$G$是平面图，那么在$F(G)$中有一个面是无界的，我们称之为外面；其他面都是有界的，我们称之为内面．

使用Jordan曲线定理可以证明：包含$K_5$-细分和$K_{3,3}$-细分的图都不可平化．事实上，这是可平面性的充要条件，也就是著名的Kuratowski定理，该证明复杂，此处不予呈现．

Kuratowski定理 一个图是可平面的当且仅当它不包含$K_5$-细分和$K_{3,3}$-细分．

与之相关的另一个重要定理就是Wagner定理．

Wagner定理 一个图是可平面的当且仅当它不包含$K_5$-minor和$K_{3,3}$-minor．

---

返回【图论笔记】